#include<string.h>
#include<vector>
#include<algorithm>
#include<functional>
#include<utility>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<limits.h>

using namespace std;

//Define localizacao
typedef struct{
  int x;
  int y;
} Endereco;

//Variaveis globais 
vector<Endereco> clientes;
vector<vector<int> > montanha;
Endereco pizzaria;
vector<vector<pair<int, int> > > grafo;
vector<int> tempos;
vector<pair<int,int> > marks;
int N,M,custo;


//Le os dados referente a regiao montanhosa    
void le_montanha(){

    char especial;
    Endereco aux;

    scanf("%d %d\n", &M, &N);
    montanha.clear();
    grafo.clear();
    clientes.clear();
    tempos.clear();
    montanha.resize(M);

    for ( int i=0; i<M; i++ )
    {

      montanha[i].resize(N);

      for ( int j=0; j<N; j++ ) 
      {
        scanf("%c", &especial);

        if ( especial == '$' ) 
        {
          montanha[i][j] = -2;
          aux.x = j; aux.y = i;
          clientes.push_back(aux);
        }
        else if ( especial == 'X' ) 
        {
          //marca a pizzaria no grid da montanha
          montanha[i][j] = -1;
          pizzaria.x = j; pizzaria.y = i;
        }
        else
          montanha[i][j] = especial - 48;
      }
      scanf("%*c");
    }

}    


//encontra o custo de um ponto para o outro
int encontraCusto(int x1, int y1, int x2, int y2) {
  int custo = 0;
  if ( montanha[x1][y1] >= 0 ) {
    if ( montanha[x2][y2] >= 0 ) {
       
        if (abs(montanha[x1][y1] - montanha[x2][y2]) == 0) 
        {
               custo = 1;
        }else custo = INT_MAX;

        if (abs(montanha[x1][y1] - montanha[x2][y2]) == 1) 
        {
               custo = 3;
        }else custo = custo;


    } else 
      custo = 2;
  } else if ( montanha[x1][y1] < 0 ) {
    if ( montanha[x2][y2] < 0 )
      custo = 2;
    else
      custo = 2;
  }

  return custo;
}


//monta o grafo decaminhos
void monta_grafo () {
    for ( int i=0; i<M; i++ )
    {
        for ( int j=0; j<N; j++ )
        {
            if ( i > 0 )
            {
                custo = encontraCusto(i, j, i-1, j);
                grafo[i*N+j].push_back(make_pair((i-1)*N+j, custo));
            }
            if ( j < N-1 )
            {
                custo = encontraCusto(i, j, i, j+1);
                grafo[i*N+j].push_back(make_pair(i*N+j+1, custo));
            }
            if ( i < M-1 )
            {
                custo = encontraCusto(i, j, i+1, j);
                grafo[i*N+j].push_back(make_pair((i+1)*N+j, custo));
            }
            if ( j > 0 )
            {
                custo = encontraCusto(i, j, i, j-1);
                grafo[i*N+j].push_back(make_pair(i*N+j-1, custo));
            }
        }
    }
}

//divide a entrega das pizza e retorna o tempo do motoqueiro mais lento
int divideEntrega(int bin) {

  vector<int> motoqueiroA;
  vector<int> motoqueiroB;

  int r,q,i;
  int total_motoqueiroA = 0;
  int total_motoqueiroB = 0;
  r = 0;
  q = bin;
  i = 0;

  while ( q > 0 ) {
    r = q%2;
    if ( r == 0 )
      motoqueiroB.push_back(tempos[tempos.size()-i-1]);
    else
      motoqueiroA.push_back(tempos[tempos.size()-i-1]);
    q = q/2;
    i++;
  }

  for ( int i=0; i<motoqueiroA.size()-1; i++ )
  {
    total_motoqueiroA += motoqueiroA[i]*2;
  }

  total_motoqueiroA += motoqueiroA[motoqueiroA.size()-1];

  for ( int i=0; i<motoqueiroB.size()-1; i++ ) 
  {
    total_motoqueiroB += motoqueiroB[i]*2;
  }

  total_motoqueiroB += motoqueiroB[motoqueiroB.size()-1];

  //retorna o maior tempo
  return max(total_motoqueiroA, total_motoqueiroB); 
}


//encontro o menor tempo possivel
int melhorTempo() {

  int bin = pow(2,(tempos.size()-1));
  int max = bin*2-1;
  int menor_tempo = INT_MAX;
  int solution;

  if ( tempos.size() == 1 )
    return tempos[0];


  while ( bin < max )
  {
    solution = divideEntrega(bin);

    if ( solution < menor_tempo )
      menor_tempo = solution;

    bin++;
  }

  return menor_tempo;
}

//encontra tempo gasto
int encontraTempo(int a, int b) {
  
  int u,v;
  int alt;

  marks.resize(grafo.size());
  for ( int i=0; i<grafo.size(); i++ ) {
    marks[i] = make_pair(INT_MAX, -1);
  }
  marks[a].first = 0;
  
  vector<int> restante;
  vector<int>::iterator it;
  restante.resize(grafo.size());
  for ( int i=0; i<grafo.size(); i++ )
    restante[i] = i;

  while ( !restante.empty() ) {
    u = -1;
    for ( int i=0; i<restante.size(); i++ ) {
      if ( restante[i] != -1 )
        if ( u == -1 || (marks[i].first < marks[u].first) )
          u = i;
    }
    if ( marks[u].first == INT_MAX || u == b)
      return marks[b].first;
    
    restante[u] = -1;

    for ( int i=0; i<grafo[u].size(); i++ ) {
      if ( restante[grafo[u][i].first] != -1 ) {
        if ( grafo[u][i].second == INT_MAX )
          alt = INT_MAX;
        else
          alt = marks[u].first + grafo[u][i].second;
        if ( alt < marks[grafo[u][i].first].first ) {
          marks[grafo[u][i].first].first = alt;
          marks[grafo[u][i].first].second = u;
        }
      }
    }
  }
}

void monta_tempos(){

    for ( int i=0; i<clientes.size(); i++ )
    {
        tempos[i] = encontraTempo(pizzaria.y*N+pizzaria.x, clientes[i].y*N+clientes[i].x);
    }

    sort(tempos.begin(), tempos.end(), greater<int>() );

    if ( tempos[0] == INT_MAX ) 
    {
        printf("-1\n");
    } else
        printf("%d\n", melhorTempo());
}

//Main
int main() {
  
  int cases;

  scanf("%d\n", &cases);

  while ( cases > 0 ) {
   
    le_montanha();

    grafo.resize(M*N);

    monta_grafo();

    tempos.resize(clientes.size());

    monta_tempos();

    cases--;
  }
}
